package leetcode;

import java.util.*;

public class lc131 {
    public static void main(String[] args) {
        System.out.println(partition("aab"));
    }
    public static List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(s, ans, path, 0);
        return ans;
    }
    public static void dfs(String s, List<List<String>> ans, List<String> path, int index){
        if(index >= s.length()){
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if(isHW(s.substring(index, i + 1))){
                path.add(s.substring(index, i + 1));
            }else
                continue;
            dfs(s, ans, path, i + 1);
            path.remove(path.size() - 1);
        }
    }
    public static boolean isHW(String s){
        if(s.length() == 0)
            return  false;
        int i = 0;
        int j = s.length() - 1;
        while(i < j){
            if(s.charAt(i) != s.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }
}
